package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
 *
 * @param root TreeNode类
 * @param sum int整型
 * @return int整型二维数组
 */
var ans [][]int = make([][]int, 0)

func pathSum(root *TreeNode, sum int) [][]int {
	// write code here
	dfs(root, sum)
	return ans
}

var a []int = make([]int, 0)

func dfs(root *TreeNode, sum int) {
	if root == nil {
		return
	}
	a = append(a, root.Val)
	sum = sum - root.Val
	if root.Left == nil && root.Right == nil {
		if sum == 0 {
			ans = append(ans, append([]int(nil), a...))
		}
		a = a[:len(a)-1]
		return
	}
	dfs(root.Left, sum)
	dfs(root.Right, sum)
	a = a[:len(a)-1]
}
